#ifndef __BINARYSORT_TREE_H__
#define __BINARYSORT_TREE_H__

#include <iostream>
#include <vector>

using namespace std;

class Node
{
public:
    Node(int v);
    ~Node();

    int val;
    Node *left, *right;
};
Node::Node(int v)
    : val(v), left(nullptr), right(nullptr)
{
}
Node::~Node()
{
    left = right = nullptr;
    val = 0;
}

class Tree
{
public:
    Tree();

    static void insert(Node *&, int);
    static Node *find(Node *, int);
    static void delTree(Node *&, int);
    static void delNode(Node *&);
    static void inOrderTraversal(Node *);
    static int level(Node *);
    
    Node *root;
};

Tree::Tree()
    : root(nullptr)
{
}

Node *Tree::find(Node *p, int v)
{
    if (nullptr == p)
        return p;
    else if (v == p->val)
        return p;
    else if (p->val > v)
        return find(p->left, v);
    else if (p->val < v)
        return find(p->right, v);
}

void Tree::insert(Node *&p, int v)
{
    if (nullptr == p)
        p = new Node(v);
    else if (p->val > v)
        insert(p->left, v);
    else if (p->val < v)
        insert(p->right, v);
}

void Tree::delTree(Node *&p, int v)
{
    if (nullptr == p)
        return;
    else if (p->val == v)
        delNode(p);
    else if (p->val > v)
        delTree(p->left, v);
    else if (p->val < v)
        delTree(p->right, v);
}

void Tree::delNode(Node *&p)
{
    Node *q, *s;
    if (nullptr == p->right)
    {
        q = p;
        p = p->left;
        delete q;
        return;
    }
    else if (nullptr == p->left)
    {
        q = p;
        p = p->right;
        delete q;
        return;
    }
    else
    {
        q = p;
        s = p->left;
        while (s->right)
        {
            q = s;
            s = s->right;
        }
        p->val = s->val;
        if (q != p)
        {
            q->right = s->left;
        }
        else
        {
            q->left = s->left;
        }
        delete s;
        return;
    }
}

void Tree::inOrderTraversal(Node *p)
{
    if (nullptr == p)
        return;
    if (p->left)
        inOrderTraversal(p->left);
    cout << p->val << " ";
    if (p->right)
        inOrderTraversal(p->right);
}

int Tree::level(Node *p)
{
    if (nullptr == p)
        return 1;
    int ll = level(p->left);
    int lr = level(p->right);
    int max = lr > ll ? lr : ll;
    return max + 1;
}

#endif